﻿#include<iostream>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<algorithm>
#include <array>
#include <numeric>

using namespace std;


// 以下是两个数组的 背包问题 问题专题
// 
// 几乎所有背包问题都要利用滚动数组做空间上，这是因为单个物品的体积和背包的体积相差非常大
// 
// 第 49 题 ################################################################################################
// 链接：https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e?tpId=230&tqId=38964
// 
//DP41 【模板】01背包
//描述  
// 你有一个背包，最多能容纳的体积是V。
// 现在有n个物品，第i个物品的体积为vi，价值为wi
// 输出要回答下面两个问题
// （1）求这个背包至多能装多大价值的物品？
// （2）若背包恰好装满，求至多能装多大价值的物品？
// 输入描述：
// 第一行两个整数n和V，表示物品个数和背包体积。
// 接下来n行，每行两个数vi 和 wi,表示第i个物品的体积和价值。
//数据范围：1 ≤ v ≤ 1000 ，1 ≤ n ≤ 1000 ，1 ≤ vi ≤1000 ，1 ≤ wi ≤ 1000
//输出描述：
// 输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。
//示例1 
//输入：
//3 5
//2 10
//4 5
//1 4
// 输出：
//14
//9
// 说明：
//装第一个和第三个物品时总价值最大，但是装第二个和第三个物品可以使得背包恰好装满且总价值最大。
//
// 初步分析：
// 总可以通过在前i个物品中 不超过 j 体积的条件下的最优方案，退出当前的最优方案
// dp 表示：从前i 个物品中挑选，总体积不超过j 的所有选法中，能够挑选出来的最大价值

// #include <array>
// #include <cstring>
// #include <iostream>
// #include <vector>
// using namespace std;

// int main() {
//     int noft, totalv;
//     cin >> noft >> totalv;
//     int n = noft;
//     array<int, 1010> v = {0};
//     array<int, 1010> w = {0};
//     for(int i = 1; i <= n; ++i){
//         cin >> v[i] >> w[i];
//     }
//     // dp表示:从前i个物品中挑选，总体积不超过j 的所有选法中，能够挑选出来的最大价值
//     int dp[1010][1010] = {0};
//     for (int i = 1; i <= n; ++i) {
//         for (int j = 1; j <= totalv; ++j) {
//             if (j >= v[i]) {
//                 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
//             }
//             else{
//                 dp[i][j] = dp[i - 1][j];
//             }
//         }
//     }
//     cout << dp[n][totalv] << endl;
//     // dp2表示:从前i个物品中挑选，总体积正好等于j 的所有选法中，能够挑选出来的最大价值
//     memset(dp, 0, sizeof(dp));
//     for(int j = 1; j <= totalv; ++j){
//         dp[0][j] = -1;
//     }
//     for (int i = 1; i <= n; ++i) {
//         for (int j = 1; j <= totalv; ++j) {
//             if ((j >= v[i]) && dp[i - 1][j - v[i]] != -1) {
//                 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
//             }
//             else{
//                 dp[i][j] = dp[i - 1][j];
//             }
//         }
//     }
//     if(dp[n][totalv] == -1){
//         cout << 0;
//     }
//     else{
//         cout << dp[n][totalv];
//     }
// }
// // 64 位输出请用 printf("%lld")

// 下面是第49题用滚动数组进行优化后的代码
//int main() {
//    int noft, totalv;
//    cin >> noft >> totalv;
//    int n = noft;
//    array<int, 1010> v = { 0 };
//    array<int, 1010> w = { 0 };
//    for (int i = 1; i <= n; ++i) {
//        cin >> v[i] >> w[i];
//    }
//    // dp表示:从前i个物品中挑选，总体积不超过j 的所有选法中，能够挑选出来的最大价值
//    int dp[1010] = { 0 };
//    for (int i = 1; i <= n; ++i) {
//        // for (int j = totalv; j >= 1; --j) {
//        //     if (j >= v[i]) {
//        //         dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
//        //     }
//        // }
//        for (int j = totalv; j >= v[i]; --j) {
//            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
//        }
//    }
//    cout << dp[totalv] << endl;
//    // 下面的dp表示:从前i个物品中挑选，总体积正好等于j 的所有选法中，能够挑选出来的最大价值
//    memset(dp, 0, sizeof(dp));
//    for (int j = 1; j <= totalv; ++j) {
//        dp[j] = -1;
//    }
//    for (int i = 1; i <= n; ++i) {
//        // for (int j = totalv; j >= 1; --j) {
//        //     if ((j >= v[i]) && dp[j - v[i]] != -1) {
//        //         dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
//        //     }
//        // }
//        for (int j = totalv; j >= v[i]; --j) {
//            if (dp[j - v[i]] != -1) {
//                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
//            }
//        }
//    }
//    if (dp[totalv] == -1) {
//        cout << 0;
//    }
//    else {
//        cout << dp[totalv];
//    }
//}


// 第 50 题 ################################################################################################
//416. 分割等和子集
//给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
//示例 1：   输入：nums = [1, 5, 11, 5]     输出：true
//解释：数组可以分割成[1, 5, 5] 和[11] 。
// class Solution {
// public:
//     bool canPartition(vector<int>& nums) {
// // dp 表示从[0, i]中所有选数的选法中，是否有一种选法的和等于 j
// // dp[1][1]T dp[1][2]F dp[1][3]F dp[1][4]F dp[1][5]F dp[1][6]F dp[1][7]F dp[1][8]F dp[1][9]F dp[1][10]F dp[1][11]F
// // dp[2][1]T dp[2][2]F dp[2][3]F dp[2][4]F dp[2][5]T dp[2][6]T dp[2][7]F dp[2][8]F dp[2][9]F dp[2][10]F dp[2][11]F
// // dp[3][1]T dp[3][2]F dp[3][3]F dp[3][4]F dp[3][5]T dp[3][6]T dp[3][7]F dp[3][8]F dp[3][9]F dp[3][10]T dp[3][11]T

//         int n = nums.size();
//         int totalnum = accumulate(nums.begin(), nums.end(), 0);
//         if(totalnum % 2){return false;}
//         int target = totalnum / 2;
//         // vector<vector<bool>> dp(n + 1, vector<bool>(target + 1));
//         bool dp[210][200000] = {0};
//         for(int i = 0; i <= n; ++i){
//             dp[i][0] = true;
//         }
//         for(int i = 1; i <= n; i++){
//             for(int j = 1; j <= target; ++j){
//                 if(j >= nums[i - 1]){
//                     dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
//                 }
//                 else{
//                     dp[i][j] = dp[i - 1][j];
//                 }
//                 if(j == target && dp[i][j]){
//                     return true;
//                 }
//             }
//         }
//         return dp[n][target];
//     }
// };

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // dp 表示从[0, i]中所有选数的选法中，是否有一种选法的和等于 j
        int n = nums.size();
        int totalnum = accumulate(nums.begin(), nums.end(), 0);
        if (totalnum % 2) { return false; }
        int target = totalnum / 2;
        bool dp[20000] = { false };
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = target; j >= nums[i - 1]; --j) {
                dp[j] = dp[j] || dp[j - nums[i - 1]];
                if (j == target && dp[j]) {
                    return true;
                }
            }
        }
        return false;
    }
};

// 第 51 题 ################################################################################################
// 494. 目标和
// 给你一个非负整数数组 nums 和一个整数 target 。
// 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
// 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
// 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
// 示例 1：       输入：nums = [1, 1, 1, 1, 1], target = 3       输出：5
// 解释：一共有 5 种方法让最终目标和为 3 。
// - 1 + 1 + 1 + 1 + 1 = 3
// + 1 - 1 + 1 + 1 + 1 = 3
// + 1 + 1 - 1 + 1 + 1 = 3
// + 1 + 1 + 1 - 1 + 1 = 3
// + 1 + 1 + 1 + 1 - 1 = 3
//
//  用背包问题的思想，很容易找到一个数组中的所有序列中，那些序列和等于aim的方案数
//  此时可以考虑将   494  这个题进行等价变换，变换成上面那句话所说的问题
//  由于这个序列中的每个数的符号只有两种选择，正号和负号
//  选择为正号的那些数归为一类，求其和，得到正号和，记为 posisum
//  选择为负号的那些数归为一类，求其和，得到负号和，记为 negasum
//  那么 posisum + negasum = totalsum  且 posisum - negasum = target
// 
//  那么 posisum = (totalsum + target) / 2
//

// 动态规划的求解方法
// 先转化为从数组中挑出一些数，加起来等于 posisum = (totalsum + target) / 2 的方案数
// 需要注意的是：下面是两种不同的方案（不考虑滚动数组的空间优化）
// 方案一：
//     更新dp表示不考虑看到 0的情况，看到一个0就将multiplier 乘等上2，最后返回结果时再乘上multiplier
class Solution4 {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        int multiplier = 1;
        int totalsum = accumulate(nums.begin(), nums.end(), 0);
        if ((totalsum + target) % 2 || (totalsum + target) < 0) { return 0; }
        int posisum = (totalsum + target) / 2;
        // dp 表示从[0, i] 中选取一些数，加起来等于 j 的方案数
        // int dp[25][20020] = {0};
        int dp[20020] = { 0 };
        // for(int i = 0; i <= n; i++){
        //     dp[i][0] = 1;
        // }
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (nums[i - 1] == 0) {
                multiplier *= 2;
            }
            // for(int j = 1; j <= posisum; ++j){
            //     if(j >= nums[i - 1] && nums[i - 1]){
            //         dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
            //     }
            //     else{
            //         dp[i][j] = dp[i - 1][j];
            //     }
            // }
            for (int j = posisum; j >= nums[i - 1]; --j) {
                if (nums[i - 1]) {
                    dp[j] = dp[j] + dp[j - nums[i - 1]];
                }
            }
        }
        return dp[posisum] * multiplier;
    }
};

// 方案二：
//     更新dp表时从 j = 0开始更新，那么当dp[i][0]就是 dp [i - 1][0] * 2;
class Solution5 {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        int totalsum = accumulate(nums.begin(), nums.end(), 0);
        if ((totalsum + target) % 2 || (totalsum + target) < 0) { return 0; }
        int posisum = (totalsum + target) / 2;
        // dp 表示从[0, i] 中选取一些数，加起来等于 j 的方案数
        // int dp[25][20020] = {0};
        int dp[20020] = { 0 };

        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            // for(int j = 0; j <= posisum; ++j){
            //     if(j >= nums[i - 1]){
            //         dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
            //     }
            //     else{
            //         dp[i][j] = dp[i - 1][j];
            //     }
            // }
            for (int j = posisum; j >= nums[i - 1]; --j) {
                dp[j] = dp[j] + dp[j - nums[i - 1]];
            }
        }
        return dp[posisum];
    }
};

int main()
{
    Solution4 solu;
    vector<int> nums = { 9,7,0,3,9,8,6,5,7,6 };
    solu.findTargetSumWays(nums, 2);
}

